/*************************************************************************
 * File Name:    test.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-1 20:26:58
 * 
 * Description:  
 |------------------------------------------------------------------------ 
 | Linked List Cycle II
 |
 | Given a linked list, return the node where the cycle begins.
 | If there is no cycle, return null.
 |
 | Follow up:
 | Can you solve it without using extra space?
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL) return NULL;
        
        ListNode *p1, *p2;
        
        p1 = p2 = head;
        while (true) {
            p1 = p1->next;
            p2 = p2->next;
            if (p2 == NULL) return NULL;
            p2 = p2->next;
            if (p2 == NULL) return NULL;
            
            if (p1 == p2) break;
        }
        ListNode *ans = head;
        while (ans != p1) {
            ans = ans->next;
            p1 = p1->next;
        }
        return ans;
    }
};

